Within the Internet community there are several initiatives towards improving different aspects of the Internet. Some of the major issues are: (1) extending the service model, (2) routing and forwarding efficiency and scalability, and (3) operations and management.
All of these are important to the continued growth and success of the Internet. The present application is related to a combination of two emerging technologies, MultiProtocol Label Switching (MPLS) and Bandwidth Brokers (BB), which have great potential in the context of all three mentioned issues. The main focus of the present invention is on the implementation of a bandwidth guaranteed service called Virtual Leased Line, or VLL.
The following section briefly describes the two technologies MPLS and BB. MPLS is undergoing standardisation in the Internet Engineering Task Force (IETF) while there is currently no formal effort to standardise Bandwidth Brokers.
The MPLS working group of the IETF was started in response to the label-switching trend among router vendors back in 1997.At the time, there existed several proprietary implementations and the need for standardisation was identified.
MPLS is a method that integrates the label-switching forwarding paradigm with network layer routing. In MPLS, connection-oriented switching is provided based on IP routing and control protocols.
In short, MPLS operates as follows:                Associate labels with specific streams of forward equivalence classes (FECs).        Distribute the labels and their FEC bindings across the network, the MPLS domain, to establish a Label Switched Path (LSP).        Assign packets one or more labels (a stack of labels) when entering the domain.        Forward packets through the domain based upon the labels.        
Core components of MPLS are semantics of labels, forwarding methods and label distribution methods.
The explicit routing feature of multiprotocol label switching (MPLS) was introduced to address the shortcomings associated with current IP routing schemes, which are hampered by the requirement to forward packets based only on destination addresses along shortest paths computed using mostly static and traffic characteristic independent link metrics. While this shortest path routing is sufficient to achieve connectivity, it does not always make good use of available network resources and is not satisfactory from a traffic-engineering point of view. A prime problem is that some links on the shortest path between certain ingress-egress pairs may get congested while links on possible alternate paths remain free. Even in the best effort model, this means that available network resources are not being used well, resulting in higher delays, and there is a potential for providing better quality of service (QoS) with the same network infrastructure.
In MPLS networks, when bandwidth-guaranteed label-switched paths (LSPs) are set up, shortest path routing with fixed link metrics can cause LSP set-up requests to be rejected, even though these requests may have been admissible using a different routing scheme. Therefore, routing schemes that can make better use of network infrastructure are needed. This better use of network infrastructure while maintaining QoS guarantees is the primary objective of traffic engineering. MPLS networks' ability to control the path from ingress node to egress node to optimise utilisation of network resources and enhance performance is regarded as a primary justification for the use of MPLS.
In MPLS packets are encapsulated, at ingress points, with labels that are then used to forward the packets along LSPs. Service providers can use bandwidth-guaranteed LSPs as components of an IP virtual private network (VPN) service with the bandwidth guarantees used to satisfy customer service level agreements (SLAs). These LSPs can be thought of as virtual traffic trunks that carry flow aggregates generated by classifying the packets arriving at the edge or ingress routers of an MPLS network into forwarding equivalence classes (FECs). Classification into FECs is done using packet filters that examine header fields such as source address, destination address, and type-of-service bits. The filter rules determining the FECs can be established in a variety of ways such as downloading from a policy or route server, or interaction with routing protocols. The purpose of classifying packets into FECs is to enable the service provider to traffic engineer the network and route each FEC in a specified manner. This is done by mapping arriving packets belonging to an FEC to one of the LSPs associated with the FEC. Before mapping packets onto an LSP, the LSP is set up, along an explicit route if specified, using a signalling protocol permitting resource reservation such as Resource Reservation Setup Protocol (RSVP).
The cost-efficiency of IP networks is partly achieved through the connection-less traffic model resulting in efficient sharing of resources. However, this model does not allow for quality guarantees, without additional functionality for service differentiation in network devices. In recent years such functionality has become common, and static Quality of Service (QoS) configurations with it. By introducing a Bandwidth Broker (BB) into the network QoS policy management can be handled in a more flexible way.
A bandwidth broker is an entity in a network domain that manages policies for bandwidth resources. By maintaining a database of the domain's resources it provides admission control decisions on QoS service requests. It is also responsible for configuring the network to meet the granted policies. It may be able to communicate with bandwidth brokers in neighbouring domains, allowing QoS services spanning several domains.
In WO-00/30295 is described a method for providing admission control and network Quality of Service (QoS).
In the background section of the WO-application drawbacks with prior art techniques are discussed focusing inter alia on the scalability concerns leading to the development of the Differentiated Services (DiffServ) architecture. Diffserv allows distinct levels of network service to be provided to different traffic. However, rather than storing per-flow state information on each intermediate node in the network between the sender and the receiver(s), routers within a DiffServ network handle packets on different traffic flows by applying different per-hop behaviours (PHBs) based upon the setting of bits in the TOS field of each packet's IP header. In this manner, many traffic flows may be aggregated into one of a small number of predefined PHBs, thereby allowing a reduction in the amount of processing and storage associated with packet classification and forwarding. While solving the scalability issues, DiffServ fails to provide adequate guidance with regard to implementation of an admission control policy.
One approach for performing admission control suggested by the DiffServ framework involves using a centralised bandwidth broker. The centralised bandwidth broker has control over the entire domain and centrally handles bandwidth allocation requests. The following example briefly describes the work performed by a bandwidth broker.
A sender wishing to establish a particular level of service for a data flow between it and a receiver transmits an indication of its requirements to a centralised bandwidth broker. The centralised bandwidth broker validates the request against policies, compares the request against the current allocation of bandwidth for accepted traffic, and configures the edge devices with information needed to mark and shape (or police) incoming packets for the flow. Subsequently, as packets that are part of the established data flow traverse the DiffServ network cloud, intermediate core devices apply a PHB that corresponds to the DiffServ service level indicated in the packet header.
In WO-00/30295 the object is to achieve a network that handles the shortcomings of using a centralised broker, e.g. that a useful centralised broker may be very complex and has limited capability to handle bandwidth requests for multicast sessions.
Below is described the current state of the art in using MPLS alone and a combination of Bandwidth Brokers and MPLS. The main focus of this section is on extending the service model (i.e., implementing QoS).
The MPLS standards cover mechanisms and protocols that provide the basic tools for MPLS networking. Given the current standards and available equipment, many MPLS networks are manually routed. In such a network the main advantages of using MPLS are fast fail over-routing and a clear separation of inter- and intra-domain routing. These properties of MPLS do not really qualify as QoS-enablers, but are good examples of how MPLS is used.
Another common application of MPLS is for VPN set-up by administrative tools (for example Orchestream). In these applications the main advantage is that the shared network is partitioned into private VPNs using the MPLS LSPs.
There is a system known as Routing and Traffic Engineering Server (RATES) which is described as an MPLS traffic-engineering server. The system is described by Aukia, Kodialam, Koppol, Lakshman, Sarin and Suter in: “RATES: A server for MPLS Traffic Engineering”, IEEE Network Magazine, May 2000. Referred to as [RATES] below. The model under which RATES operates is that service requests are passed to an engine that evaluates them and possibly implements the service in the network. A service request is defined by source and destination addresses (or prefixes) and a bandwidth constraint. [RATES] defines a routing algorithm, which tries to find a path that can accommodate the requests. This is in contrast to other systems, which merely use the routes available from layer three routing (normally shortest paths).
A current state of the art Bandwidth Broker (BBOLOV) system is described in Olov Schelén, Quality of Service Agents in the Internet,Doctoral Thesis, Department of Computer Science and Electrical Engineering, Division of Computer Communication, Luleå University of Technology, Luleå, 1998.Referred to as [OLOV] below.
BBOLOV has many similarities to RATES. The BBOLOV is described in the context of DiffServ networks while RATES operates in MPLS. Apart from that basic difference, these two systems operate under the same model; receive service requests, evaluate them and possibly implement the service. This is schematically illustrated in FIG. 1. The major difference between these two systems is the underlying networking technology.
An important property of both RATES and BBOLOV is the implementation of path sensitive admission control. Both systems make sure that all links on a path have enough forwarding resources to keep up with the service request. Path sensitive admission control (by a centralised entity) requires detailed knowledge of the network topology, or rather, the routing topology. Both RATES and BBOLOV use the straightforward method of peering as a link state-router, which provides a dynamic and detailed view of the routing topology.
Routers in a link state-domain continuously synchronise topology information with each other. All routers have all information needed to build a complete view of the domain topology. Changes in one part of the network are flooded across the entire domain, making sure that all routers have information that is up to date. Peering as a link state-router simply means that a host takes part in the information exchange to receive all information dynamically. This can be done passively, which means the host does not advertise any information of its own.
Each RATES instance is limited to one flat link state-domain (e.g. an Open Shortest Path First (OSPF) area), while BBOLOV is assumed to control an entire routing domain, which may utilise hierarchical routing. In the case of hierarchical routing, BBOLOV relies on routing probes, which act as routing peers within flat link state-domains to collect routing information.
Using systems like these, which use the MPLS and BB concepts in combination, it is possible to achieve dynamic QoS service set-up and tear-down in either DiffServ or MPLS networks.
The state of the art in MPLS and the combination of MPLS traffic-engineering servers and bandwidth brokers have some shortcomings, which is briefly discussed in the following.
An overall object of the present invention is focused on the implementation of a VLL service with bandwidth guarantees, which requires path sensitive admission control. For the service to be as useful as possible it is important that service control is dynamic and managed automatically. The service issues focused on are:                End to end-services.        Resource planning over time.        
The end-to-end issue is of great importance when service requests span multiple network provider domains and possibly a mix of DiffServ and MPLS networks. A service that is only available within one provider domain is unlikely to be successful in a world where global services of all kinds are increasingly important.
Planning resources over time is an important issue if bandwidth guaranteed services on otherwise shared networks are to become a credible alternative to more rigid solutions such as leased lines or circuit switched networks. Business users will certainly require the ability to plan ahead when it comes to QoS. A business whose mission critical applications fail due to unavailability of network QoS is very likely to abandon the failing provider.
During the development of the Bandwidth Broker model the initial focus were end-to-end services. A Bandwidth Broker is responsible for the bandwidth resources within its domain and can trade bandwidth with brokers in neighbouring domains. These ideas are not tightly coupled to the way admission control is performed. However, to implement services like the bandwidth guaranteed VLL, a very specific admission control method is required. The above-mentioned state of the art MPLS traffic engineering server, RATES, covers only one link state-area which is in fact only a small part of a provider domain. This means that several RATES systems are needed to cover a single domain.
The Bandwidth Broker BBOLOV in the Olov Schelen thesis identified above defines a method, which enables planning of a VLL service over time. Admission control, which is at the core of implementing the service, is performed with time as an input parameter.
The [RATES] system does not consider time at all. Admission control for service requests is done at the time the request is made. The inability to plan over time requires a compromise in network utilisation versus customer values. For example, if a customer relies on the availability of bandwidth resources for a business event a week ahead from now, he needs to make the request as soon as possible to make sure that his request will be admitted. Awaiting the event, the customer will be paving for a service that he has no use for.
For MPLS networks, there is currently no known solution to this problem.
In Schelén O et.al. “Performance of QoS agents for provisioning network resources”, Quality of Service, 1999. IWQOS ′99. 1999 Seventh international workshop on London UK 31 May-4 June 1999, Piscataway, NJ, USA, IEEE, US, 31 May 1999, pages 17–26, ISBN: 07803-5671-3, discloses a method for providing resource reservations for VLLs between network domains. The reservations may be scheduled over time and each reserved path may have a predetermined QoS. A Qos agent (or Bandwidth Broker) performs admission control in its domain. However, this paper does not disclose a method for performing the resource reservations in a network having heterogeneous MPLS domains.
Thus, a first object of the present invention is to achieve a method that implements end-to-end services (of the VLL kind) across a set of heterogeneous MPLS domains.
A second object of the present invention is to achieve a method implementing a resource planning of a VLL service over time.